home *** CD-ROM | disk | FTP | other *** search
/ Compendium Deluxe 2 / LSD and 17bit Compendium Deluxe - Volume II.iso / a / prog / cprog / voronoi.lha / geometry.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-03-19  |  3.6 KB  |  184 lines
  1. #
  2. #include "defs.h"
  3. #include <math.h>
  4.  
  5. geominit()
  6. {
  7. struct Edge e;
  8. float sn;
  9.  
  10.     freeinit(&efl, sizeof e);
  11.     nvertices = 0;
  12.     nedges = 0;
  13.     sn = nsites+4;
  14.     sqrt_nsites = sqrt(sn);
  15.     deltay = ymax - ymin;
  16.     deltax = xmax - xmin;
  17. }
  18.  
  19.  
  20. struct Edge *bisect(s1,s2)
  21. struct    Site *s1,*s2;
  22. {
  23. float dx,dy,adx,ady;
  24. struct Edge *newedge;
  25.  
  26.     newedge = (struct Edge *) getfree(&efl);
  27.  
  28.     newedge -> reg[0] = s1;
  29.     newedge -> reg[1] = s2;
  30.     ref(s1); 
  31.     ref(s2);
  32.     newedge -> ep[0] = (struct Site *) NULL;
  33.     newedge -> ep[1] = (struct Site *) NULL;
  34.  
  35.     dx = s2->coord.x - s1->coord.x;
  36.     dy = s2->coord.y - s1->coord.y;
  37.     adx = dx>0 ? dx : -dx;
  38.     ady = dy>0 ? dy : -dy;
  39.     newedge -> c = s1->coord.x * dx + s1->coord.y * dy + (dx*dx + dy*dy)*0.5;
  40.     if (adx>ady)
  41.     {    newedge -> a = 1.0; newedge -> b = dy/dx; newedge -> c /= dx;}
  42.     else
  43.     {    newedge -> b = 1.0; newedge -> a = dx/dy; newedge -> c /= dy;};
  44.  
  45.     newedge -> edgenbr = nedges;
  46.     out_bisector(newedge);
  47.     nedges += 1;
  48.     return(newedge);
  49. }
  50.  
  51.  
  52. struct Site *intersect(el1, el2, p)
  53. struct Halfedge *el1, *el2;
  54. struct Point *p;
  55. {
  56. struct    Edge *e1,*e2, *e;
  57. struct  Halfedge *el;
  58. float d, xint, yint;
  59. int right_of_site;
  60. struct Site *v;
  61.  
  62.     e1 = el1 -> ELedge;
  63.     e2 = el2 -> ELedge;
  64.     if(e1 == (struct Edge*)NULL || e2 == (struct Edge*)NULL) 
  65.         return ((struct Site *) NULL);
  66.     if (e1->reg[1] == e2->reg[1]) return ((struct Site *) NULL);
  67.  
  68.     d = e1->a * e2->b - e1->b * e2->a;
  69.     if (-1.0e-10<d && d<1.0e-10) return ((struct Site *) NULL);
  70.  
  71.     xint = (e1->c*e2->b - e2->c*e1->b)/d;
  72.     yint = (e2->c*e1->a - e1->c*e2->a)/d;
  73.  
  74.     if( (e1->reg[1]->coord.y < e2->reg[1]->coord.y) ||
  75.         (e1->reg[1]->coord.y == e2->reg[1]->coord.y &&
  76.         e1->reg[1]->coord.x < e2->reg[1]->coord.x) )
  77.     {    el = el1; e = e1;}
  78.     else
  79.     {    el = el2; e = e2;};
  80.     right_of_site = xint >= e -> reg[1] -> coord.x;
  81.     if ((right_of_site && el -> ELpm == le) ||
  82.        (!right_of_site && el -> ELpm == re)) return ((struct Site *) NULL);
  83.  
  84.     v = (struct Site *) getfree(&sfl);
  85.     v -> refcnt = 0;
  86.     v -> coord.x = xint;
  87.     v -> coord.y = yint;
  88.     return(v);
  89. }
  90.  
  91. /* returns 1 if p is to right of halfedge e */
  92. int right_of(el, p)
  93. struct Halfedge *el;
  94. struct Point *p;
  95. {
  96. struct Edge *e;
  97. struct Site *topsite;
  98. int right_of_site, above, fast;
  99. float dxp, dyp, dxs, t1, t2, t3, yl;
  100.  
  101. e = el -> ELedge;
  102. topsite = e -> reg[1];
  103. right_of_site = p -> x > topsite -> coord.x;
  104. if(right_of_site && el -> ELpm == le) return(1);
  105. if(!right_of_site && el -> ELpm == re) return (0);
  106.  
  107. if (e->a == 1.0)
  108. {    dyp = p->y - topsite->coord.y;
  109.     dxp = p->x - topsite->coord.x;
  110.     fast = 0;
  111.     if ((!right_of_site &e->b<0.0) | (right_of_site&e->b>=0.0) )
  112.     {    above = dyp>= e->b*dxp;    
  113.         fast = above;
  114.     }
  115.     else 
  116.     {    above = p->x + p->y*e->b > e-> c;
  117.         if(e->b<0.0) above = !above;
  118.         if (!above) fast = 1;
  119.     };
  120.     if (!fast)
  121.     {    dxs = topsite->coord.x - (e->reg[0])->coord.x;
  122.         above = e->b * (dxp*dxp - dyp*dyp) <
  123.                 dxs*dyp*(1.0+2.0*dxp/dxs + e->b*e->b);
  124.         if(e->b<0.0) above = !above;
  125.     };
  126. }
  127. else  /*e->b==1.0 */
  128. {    yl = e->c - e->a*p->x;
  129.     t1 = p->y - yl;
  130.     t2 = p->x - topsite->coord.x;
  131.     t3 = yl - topsite->coord.y;
  132.     above = t1*t1 > t2*t2 + t3*t3;
  133. };
  134. return (el->ELpm==le ? above : !above);
  135. }
  136.  
  137.  
  138. endpoint(e, lr, s)
  139. struct Edge *e;
  140. int    lr;
  141. struct Site *s;
  142. {
  143. e -> ep[lr] = s;
  144. ref(s);
  145. if(e -> ep[re-lr]== (struct Site *) NULL) return;
  146. out_ep(e);
  147. deref(e->reg[le]);
  148. deref(e->reg[re]);
  149. makefree(e, &efl);
  150. }
  151.  
  152.  
  153. float dist(s,t)
  154. struct Site *s,*t;
  155. {
  156. float dx,dy;
  157.     dx = s->coord.x - t->coord.x;
  158.     dy = s->coord.y - t->coord.y;
  159.     return(sqrt(dx*dx + dy*dy));
  160. }
  161.  
  162.  
  163. int makevertex(v)
  164. struct Site *v;
  165. {
  166. v -> sitenbr = nvertices;
  167. nvertices += 1;
  168. out_vertex(v);
  169. }
  170.  
  171.  
  172. deref(v)
  173. struct    Site *v;
  174. {
  175. v -> refcnt -= 1;
  176. if (v -> refcnt == 0 ) makefree(v, &sfl);
  177. }
  178.  
  179. ref(v)
  180. struct Site *v;
  181. {
  182. v -> refcnt += 1;
  183. }
  184.